package datastructure.graph.有向图;

import datastructure.graph.最短路径.DirectedEdge;
import datastructure.graph.最短路径.EdgeWeightedDigraph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 5:17 下午
 */
public class DepthFirstOrder {

    private boolean[] marked;
    private Queue<Integer>pre;
    private Queue<Integer>post;
    private Stack<Integer>revertPost;
    private Queue<Integer>revertPostQueue;

    public DepthFirstOrder(Digraph digraph) {
        pre=new LinkedList<>();
        post=new LinkedList<>();
        revertPost=new Stack<>();
        marked=new boolean[digraph.V()];

        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]){
                dfs(digraph,v);
            }
        }
    }

    public DepthFirstOrder(EdgeWeightedDigraph digraph) {
        pre=new LinkedList<>();
        post=new LinkedList<>();
        revertPost=new Stack<>();
        marked=new boolean[digraph.V()];

        for (int i = 0; i < digraph.V(); i++) {
            if (!marked[i]){
                dfs(digraph,i);
            }
        }
    }


    private void dfs(Digraph digraph, int v) {
        marked[v]=true;
        pre.add(v);
        for (Integer w : digraph.adj(v)) {
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
        post.add(v);
        revertPost.push(v);
    }

    private void dfs(EdgeWeightedDigraph digraph,int v){
        marked[v]=true;
        pre.add(v);
        for (DirectedEdge edge : digraph.adj(v)) {
            if (!marked[edge.to()]){
                dfs(digraph,edge.to());
            }
        }
        post.add(v);
        revertPost.push(v);
    }
    public Iterable<Integer>pre(){
        return pre;
    }

    public Iterable<Integer>post(){
        return post;
    }

    public Iterable<Integer>reversePost(){
        if (revertPostQueue!=null){
            return revertPostQueue;
        }
        revertPostQueue=new LinkedList<>();
        while (!revertPost.isEmpty()){
            revertPostQueue.add(revertPost.pop());
        }
        return revertPostQueue;
    }

    public static void main(String[] args) {
        Digraph digraph = new Digraph(13);
        digraph.addEdge(0,5);
        digraph.addEdge(0,1);
        digraph.addEdge(0,6);
        digraph.addEdge(2,0);
        digraph.addEdge(2,3);
        digraph.addEdge(3,5);
        digraph.addEdge(5,4);
        digraph.addEdge(6,4);
        digraph.addEdge(6,9);
        digraph.addEdge(7,6);
        digraph.addEdge(8,7);
        digraph.addEdge(9,10);
        digraph.addEdge(9,11);
        digraph.addEdge(9,12);
        digraph.addEdge(11,12);
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
        Iterable<Integer> reversePost = depthFirstOrder.reversePost();
        System.out.println(reversePost);

        System.out.println("======后序=======");
        Queue<Integer> post = depthFirstOrder.post;
        while (!post.isEmpty()){
            System.out.println(post.poll());
        }
    }
}
